package com.cn.algorithm01;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/13 20:17
 * 将两个有序链表拼接，拼接后的链表依然有序
 * // 测试链接：https://leetcode.com/problems/merge-two-sorted-lists
 */
public class Code12_MergeTwoSortedLinkedList {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        // 边界：当至少存在一个为空时
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }

        // 两个都不为空
        // 确定head
        ListNode head = head1.val > head2.val ? head2 : head1;
        ListNode cur1 = head == head1 ? head1.next : head2.next;
        ListNode cur2 = head == head2 ? head1 : head2;
        ListNode pre = head; // 创建一个指针

        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                pre = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                pre = cur2;
                cur2 = cur2.next;
            }
        }

        // 从上方条件出来后，肯定有一个为空
        pre.next = cur1 == null ? cur2 :cur1;
        return head;
    }


}
